package backtrack;

import java.util.ArrayList;
import java.util.List;

public class Solution77 {

    private List<Integer> track = new ArrayList<>();
    private List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {
        //初始化数组
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i]=i+1;
        }

        backTrack(nums,0,k);

        return result;

    }

    public void backTrack(int[] nums,int start,int k){

        if (track.size()==k){
            result.add(new ArrayList<>(track));
        }

        if (start>= nums.length){
            return;
        }

        for (int i = start; i < nums.length; i++) {
            //做出选择
            track.add(nums[i]);
            backTrack(nums,i+1,k);
            //撤销选择
            track.remove(Integer.valueOf(nums[i]));
        }
    }

    public static void main(String[] args) {
        Solution77 solution77 = new Solution77();
        List<List<Integer>> combine = solution77.combine(4, 2);
        System.out.println("combine = " + combine);
    }
}
